﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace TooWhite.BiTree
{
    /// <summary>
    /// 二叉树类
    /// </summary>
    /// <typeparam name="T">节点数据类型参数</typeparam>
    public class BiTreeNode<T>
    {
        public BiTreeNode<T> LeftChild;
        public BiTreeNode<T> RightChild;
        public BiTreeNode<T> Parent;
        public T Data;
        public enum NodeTypeEnum
        {
            LeftChild, RightChild, NoParent
        };

        #region 查找节点
        /// <summary>
        /// 返回该节点的子节点中数据为data的节点引用
        /// </summary>
        /// <param name="data">数据域</param>
        /// <returns>节点引用</returns>
        public BiTreeNode<T> Locate(T data)
        {
            if(data.Equals(Data)) return this;

            else
            {
                BiTreeNode<T> temp = null;
                if(LeftChild != null)
                {
                    temp = LeftChild.Locate(data);
                    if(temp != null) return temp;
                }
                if(RightChild != null)
                {
                    temp = RightChild.Locate(data);
                    if(temp != null) return temp;
                }
                return null;
            }
        }

        /// <summary>
        /// 返回该节点的子节点中数据为data的节点引用
        /// </summary>
        /// <param name="data">数据域</param>
        /// <returns>节点引用</returns>
        public BiTreeNode<T> this[T data]
        {
            get
            {
                return Locate(data);
            }
        }

        #endregion

        #region 构造函数
        public BiTreeNode(T data)
        {
            Data = data;
            Parent = LeftChild = RightChild = null;
        }

        public BiTreeNode()
        {
        }
        #endregion

        #region 遍历
        /// <summary>
        /// 先序遍历
        /// </summary>
        public static void PreOrderTraverse(BiTreeNode<T> node, Action<BiTreeNode<T>> visit)
        {
            if(node == null) return;

            visit(node);
            PreOrderTraverse(node.LeftChild, visit);
            PreOrderTraverse(node.RightChild, visit);
        }

        /// <summary>
        /// 中序遍历
        /// </summary>
        public static void InOrderTraverse(BiTreeNode<T> node, Action<BiTreeNode<T>> visit)
        {
            if(node == null) return;

            PreOrderTraverse(node.LeftChild, visit);
            visit(node);
            PreOrderTraverse(node.RightChild, visit);
        }

        /// <summary>
        /// 后序遍历
        /// </summary>
        public static void PostOrderTraverse(BiTreeNode<T> node, Action<BiTreeNode<T>> visit)
        {
            if(node == null) return;

            PreOrderTraverse(node.LeftChild, visit);
            PreOrderTraverse(node.RightChild, visit);
            visit(node);
        }

        /// <summary>
        /// 层序遍历
        /// </summary>
        public static void LevelOrderTraverse(BiTreeNode<T> node, Action<BiTreeNode<T>> visit)
        {
            Queue<BiTreeNode<T>> q = new Queue<BiTreeNode<T>>();
            q.Enqueue(node);
            while(q.Count != 0)
            {
                BiTreeNode<T> t = q.Dequeue();
                visit(t);
                if(t.LeftChild != null)
                    q.Enqueue(t.LeftChild);
                if(t.RightChild != null)
                    q.Enqueue(t.RightChild);
            }
        }

        #endregion

        #region 添加子节点
        /// <summary>
        /// 添加新的孩子
        /// </summary>
        public BiTreeNode<T> AddChild(T newData, bool LeftOrRight)
        {
            BiTreeNode<T> newNode = new BiTreeNode<T> { Data = newData, Parent = this, LeftChild = null, RightChild = null };
            if(LeftOrRight)
            {
                if(this.LeftChild == null) this.LeftChild = newNode;
                else throw new Exception("节点不为空。");
            }
            else
            {
                if(this.RightChild == null) this.RightChild = newNode;
                else throw new Exception("节点不为空。");
            }
            return newNode;
        }

        /// <summary>
        /// 添加新的子树
        /// </summary>
        public BiTreeNode<T> AddChild(BiTreeNode<T> childNode, bool LeftOrRight)
        {
            if(LeftOrRight)
            {
                if(this.LeftChild == null) this.LeftChild = childNode;
                else throw new Exception("节点不为空。");
            }
            else
            {
                if(this.RightChild == null) this.RightChild = childNode;
                else throw new Exception("节点不为空。");
            }

            childNode.Parent = this;

            return childNode;
        }
        #endregion

        /// <summary>
        /// 返回一个节点的类型（是左孩子、右孩子还是没有双亲）
        /// </summary>
        public NodeTypeEnum NodeType
        {
            get
            {
                if(this.Parent == null) return NodeTypeEnum.NoParent;
                if(this == this.Parent.LeftChild) return NodeTypeEnum.LeftChild;
                if(this == this.Parent.RightChild) return NodeTypeEnum.RightChild;
                throw new Exception("未知错误");
            }
        }

        #region 控制台输出
        /// <summary>
        /// 在控制台打印以this为根节点的树
        /// </summary>
        /// <param name="shift">开始打印位置的偏移</param>
        /// <param name="step">每次偏移步进量</param>
        /// <param name="snull">表示空节点的字符串</param>
        void APrintTry(int shift = 0, int step = 4, string snull = "[NULL]")
        {
            shift++;

            string nullstr = new string(' ', step * shift) + snull;

            if(this.LeftChild != null) this.LeftChild.APrintTry(shift, step, snull);
            else Console.WriteLine(nullstr);

            this.Output(new string(' ', step * (shift - 1)), "\n");

            if(this.RightChild != null) this.RightChild.APrintTry(shift, step, snull);
            else Console.WriteLine(nullstr);
        }

        void DoPrintOnConsole(bool[] info, int depth, int step = 4)
        {
            if(LeftChild != null)
            {
                LeftChild.DoPrintOnConsole(info, depth + 1);
            }

            info[depth - 1] = true;

            for(int i = 0; i < depth; i++)
            {
                if(info[i])
                {
                    Console.Write("|" + new string(i == depth - 1 ? '-' : ' ', step - 1));
                }
                else Console.Write(new string(' ', step));
            }
            Console.WriteLine(Data);

            if(NodeType == NodeTypeEnum.RightChild || NodeType == NodeTypeEnum.NoParent) info[depth - 1] = false;

            if(RightChild != null)
            {
                RightChild.DoPrintOnConsole(info, depth + 1);
            }

            
        }

        public void PrintOnConsole()
        {
            bool[] needprint = new bool[100];

            DoPrintOnConsole(needprint, 1);
        }

        /// <summary>
        /// 控制台输出this节点的值
        /// </summary>
        /// <param name="behind">后缀字符串</param>
        /// <param name="previous">前缀字符串</param>
        public void Output(string previous = "", string behind = "")
        {
            Console.Write(previous + this.Data.ToString() + behind);
        }
        #endregion
    }
}
